package practice.Day23;

import java.util.Scanner;

/**
 * @Author quan
 * @Description 字符串距离
 * @Date 2023/6/6 22:40
 */
public class Num2_StringDistance {
    /**
     * 要求：给出两个字符串，现在要通过最少的次数，将它们变为完全相同的字符串。求最少的次数。
     * 解法：动态规划--看不懂
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String str1 = sc.next();
            String str2 = sc.next();
            //定义二维数组
            int[][] res = new int[str1.length()+1][str2.length()+1];
            //初始化
            res[0][0] = 0;
            for (int i = 1; i <=str1.length() ; i++) {
                //初始化第一列
                res[i][0] = res[i-1][0]+1;
            }
            for (int j = 1; j <=str2.length() ; j++) {
                //初始化第一行
                res[0][j] = res[0][j-1]+1;
            }
            for (int i = 1; i <=str1.length() ; i++) {
                for (int j = 1; j <=str2.length() ; j++) {
                    res[i][j] = Math.min(res[i-1][j],res[i][j-1])+1;
                    //如果当前位置字符相等
                    if(str1.charAt(i-1) == str2.charAt(j-1)){
                        res[i][j] = Math.min(res[i][j],res[i-1][j-1]);
                    }else{
                        //当前位置的字符不相等
                        res[i][j] = Math.min(res[i][j],res[i-1][j-1]+1);
                    }
                }
            }
            System.out.println(res[str1.length()][str2.length()]);
        }
    }
}
